package string;

/**
 * 计算串中所有位置的回文半径
 *
 * @author Liaorun
 */
public class Manacher {

    public static void main(String[] args) {
        System.out.println(maxLcpsLength("12321"));
    }


    /**
     * 在一个字符串每个缝隙添加一个‘#’字符，首尾也要添加
     *
     * @param str 原字符串
     * @return 添加完特殊字符后的
     */
    public static char[] manacherString(String str) {
        char[] chars = str.toCharArray();

        char[] res = new char[str.length() * 2 + 1];

        int index = 0;

        for (int i = 0; i < res.length; i++) {
            // 最低位是0(偶数) ？ ‘#’ ：下一个字符
            res[i] = (i & 1) == 0 ? '#' : chars[index++];
        }

        System.out.println(res);
        return res;
    }

    public static int maxLcpsLength(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        char[] str = manacherString(s);

        // 记录字符串的回文半径数组
        int[] pArr = new int[str.length];
        // 中心
        int c = -1;
        // 回文右边界的再往右一个位置，最右的有效区是R-1位置
        int r = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) {
            // i至少的回文区域，先给pArr[i]
            // 最小的回文半径 = 上一个回文结构右端点最大的坐标 > 当前位置坐标 ？ Math.min(当前坐标 关于 上一个右端点坐标最大的回文字符串的中心坐标 的对称点的回文半径， 上一个右端点坐标最大的回文字符串的右端点坐标 - 当前位置) ： 1；
            pArr[i] = r > i ? Math.min(pArr[2 * c - i], r - i) : 1;

            // 每种情况都尝试能不能找到更大的回文范围
            // 结束条件：右边的坐标 > 字符串长度 || 左边的字符坐标 < 0
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    // 右边的字符 == 左边的
                    // 回文半径++
                    pArr[i]++;
                } else {
                    // 没有更大的回文半径跳出循环
                    break;
                }
            }

            // 如果新位置的回文半径的右端点坐标 > 上一个位置的回文半径的右端点坐标
            if (i + pArr[i] > r) {
                // 更新最大值
                r = i + pArr[i];
                // 中心点也更新
                c = i;
            }

            // 记录最大的回文半径
            max = Math.max(max, pArr[i]);
        }

        // 没加特殊字符前的回文长度（直径） = 添加后的回文半径 - 1
        return max - 1;
    }

}
